//
// Created by Snow on 2023/3/10.
//
#include<cstdlib>
#include<cstdio>
#define MaxSize 20
typedef struct
{
    char data[MaxSize-1];//存放栈中的数据元素
    int top;//栈顶指针，即存放栈顶元素在data数组中的下标
}SqStack;//顺序栈类型
typedef struct
{
    double data[MaxSize-1];
    int top;
} SqStack1;
void InitStack(SqStack *&s)
{
    s=(SqStack *)malloc(sizeof(SqStack));//分配一个顺序栈空间，首地址存放在s中
    s->top=-1;//栈顶指针置为-1
}
void InitStack1(SqStack1 *&s)
{
    s=(SqStack1 *)malloc(sizeof(SqStack1));//分配一个顺序栈空间，首地址存放在s中
    s->top=-1;//栈顶指针置为-1
}
void DestroyStack(SqStack *&s)
{
    free(s);
}void DestroyStack1(SqStack1 *&s)
{
    free(s);
}
bool StackEmpty(SqStack *s)
{
    return (s->top==-1);
}
bool Push(SqStack *&s,char e)
{
    if(s->top==MaxSize-1)//栈满的情况，即栈上溢出
        return false;
    s->top++;//栈顶指针增一
    s->data[s->top]=e;//元素e放在栈顶指针处
    return true;
}bool Push1(SqStack1 *&s,double e)
{
    if(s->top==MaxSize-1)//栈满的情况，即栈上溢出
        return false;
    s->top++;//栈顶指针增一
    s->data[s->top]=e;//元素e放在栈顶指针处
    return true;
}
bool Pop(SqStack *&s,char &e)
{
    if(s->top==-1)//栈为空的情况，即栈下溢出
        return false;
    e=s->data[s->top];//取栈顶元素
    s->top--;//栈顶指针减一
    return true;
}bool Pop1(SqStack1 *&s,double &e)
{
    if(s->top==-1)//栈为空的情况，即栈下溢出
        return false;
    e=s->data[s->top];//取栈顶元素
    s->top--;//栈顶指针减一
    return true;
}
bool GetTop(SqStack *s,char &e)
{
    if(s->top==-1)
        return false;
    e=s->data[s->top];//取栈顶元素
    return true;
}bool GetTop1(SqStack1 *s,double &e)
{
    if(s->top==-1)
        return false;
    e=s->data[s->top];//取栈顶元素
    return true;
}
void trans(char *exp,char postexp[])
{
    char e;
    SqStack *Optr;
    InitStack(Optr);
    int i=0;
    while(*exp!='\0')
    {
        switch(*exp)
        {
            case '(':
                Push(Optr,'(');
                exp++;
                break;
            case ')':
                Pop(Optr,e);
                while(e!='(')
                {
                    postexp[i++]=e;
                    Pop(Optr,e);
                }
                exp++;
                break;
            case '+':
            case '-':
                while(!StackEmpty(Optr))
                {
                    GetTop(Optr,e);
                    if(e!='(')
                    {
                        postexp[i++]=e;
                        Pop(Optr,e);
                    }
                    else
                        break;
                }
                Push(Optr,*exp);
                exp++;
                break;
            case '*':
            case '/':
                while(!StackEmpty(Optr))
                {
                    GetTop(Optr,e);
                    if(e=='*'||e=='/')
                    {
                        postexp[i++]=e;
                        Pop(Optr,e);
                    }
                    else
                        break;
                }
                Push(Optr,*exp);
                exp++;
                break;
            default:
                while(*exp>='0'&&*exp<='9')
                {
                    postexp[i++]=*exp;
                    exp++;
                }
                postexp[i++]='#';
        }
    }
    while(!StackEmpty(Optr))
    {
        Pop(Optr,e);
        postexp[i++]=e;
    }
    postexp[i]='\0';
    DestroyStack(Optr);
}
double compvalue(char *postexp)
{
    double a,d,b,c,e=0;
    SqStack1 *Opnd;
    InitStack1(Opnd);
    while(*postexp!='\0')
    {
        switch(*postexp)
        {
            case '+':
                Pop1(Opnd,a);
                Pop1(Opnd,b);
                c=b+a;
                Push1(Opnd,c);
                break;
            case '-':
                Pop1(Opnd,a);
                Pop1(Opnd,b);
                c=b-a;
                Push1(Opnd,c);
                break;
            case '*':
                Pop1(Opnd,a);
                Pop1(Opnd,b);
                c=b*a;
                Push1(Opnd,c);
                break;
            case '/':
                Pop1(Opnd,a);
                Pop1(Opnd,b);
                if(a!=0)
                {
                    c=b/a;
                    Push1(Opnd,c);
                    break;
                }
                else
                {
                    printf("\nDivide by zero error\n");
                    exit(0);
                }
            default:
                d=0;
                while(*postexp>='0'&&*postexp<='9')
                {
                    d=10*d+*postexp-'0';
                    postexp++;
                }
                Push1(Opnd,d);
                break;
        }
        postexp++;
    }
    GetTop1(Opnd,e);
    DestroyStack1(Opnd);
    return e;
}
int main()
{
    char exp[]="(56-20)/(4+2)";
    char postexp[MaxSize];
    trans(exp,postexp);
    printf("Infix expression:%s\n",exp);
    printf("Postfix Expression:%s\n",postexp);
    printf("Value of expression:%g\n", compvalue(postexp));
    return 1;
}